package com.sun;

import java.util.List;

/**
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 */
public class Test19删除列表倒数第n个节点 {
    public static void main(String[] args) {
        ListNode19 l1 = new ListNode19(1);
        ListNode19 l2 = new ListNode19(2);
        ListNode19 l3 = new ListNode19(3);
        ListNode19 l4 = new ListNode19(4);
        ListNode19 l5 = new ListNode19(5);
        l1.next = l2;l2.next = l3;l3.next=l4;l4.next=l5;
        ListNode19 listNode = removeNthFromEnd2(l1, 2);
        pringList(listNode);

    }
    /**
     * 方法一：自己
     */
    public static ListNode19 removeNthFromEnd1(ListNode19 head, int n) {
        ListNode19 first = head;
        ListNode19 second = head;
        for (int i = 0; i < n; i++) {
            second = second.next;
        }
        while (second != null && second.next!=null){
            second = second.next;
            first = first.next;
        }
        if(second == null){
          return first.next;
        }else {
            ListNode19 del = first.next;
            first.next = del.next;
            del.next = null;
        }
        return head;
    }
    /**
     * 方法2：力扣官方，双指针
     */
    public static ListNode19 removeNthFromEnd2(ListNode19 head, int n) {
        ListNode19 dummy = new ListNode19(0,head);
        ListNode19 first = head;
        ListNode19 second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first!=null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode19 res = dummy.next;
        return res;
    }


    /**
     * 方法3：力扣网友，回溯算法
     */

    public static ListNode19 removeNthFromEnd3(ListNode19 head, int n) {
        int traverse = traverse(head, n);
        if(traverse == n)
            return head.next;
        return head;
    }

    private static int traverse(ListNode19 node, int n) {
        if(node == null)
            return 0;
        int num = traverse(node.next, n);
        if(num == n)
            node.next = node.next.next;
        return num + 1;
    }
    public static void pringList(ListNode19 listNode19){
        while (listNode19 != null){
            System.out.println(listNode19.val);
            listNode19 = listNode19.next;
        }
    }
}

class ListNode19{
    int val;
    ListNode19 next;
    ListNode19(){}
    ListNode19(int val){
        this.val = val;
    }
    ListNode19(int val, ListNode19 next){
        this.val = val;
        this.next = next;
    }

}
